The present invention relates to digital LAN and WAN traffic switches, particularly asynchronous transfer mode (ATM) switches.
An ATM cell switch takes cells from many sources, and routes them to many destinations. Such a switch may be hardware-based, or hardware- and software-based. The architecture can be generalized as shown in FIG. 1. Cells arrive on input ports 1 to Nin and are switched through a switch fabric 100 to various ones of output ports 1 to Nout.
A cell is a fixed size unit which constitutes a fraction of a larger communication. Cells come in on input ports, and get routed to output ports.
Sometimes, collisions take place between cells. That is, cells come in on two or more input ports that are destined for the same output port. There are two scenarios which describe the condition when two or more cells are destined for the same output port: (1) momentary contention or cell collision; and (2) sustained contention or congestion.
In either case, the collisions create the need for queueing, where one or more cells have to wait in line to be delivered to the output port.
With some architectures, even when there are no collisions, blocking can take place. Blocking occurs when a cell cannot be delivered because the delivery of other cells is taking up the resources necessary for the delivery of the blocked cell. This is often referred to as xe2x80x9chead of linexe2x80x9d blocking. Blocking is undesirable, since it can delay the delivery of other cells. Also, blocked cells must be queued, just like cells delayed due to collisions.
Due to these inevitable delays in delivery, a successful architecture must properly queue cells for delivery to output ports. Such queueing is also referred to as xe2x80x9cbufferingxe2x80x9d. Buffering requires buffer control. Buffer control tells buffers when to release a cell from a queue for delivery to an output port.
Even with buffer control, it is sometimes necessary to xe2x80x9cdropxe2x80x9d cells. For instance, when cells come in on input ports xe2x80x9c1xe2x80x9d and xe2x80x9c2xe2x80x9d, all destined for output port xe2x80x9c3xe2x80x9d, it is often the situation that more cells come in than can be output from port xe2x80x9c3xe2x80x9d. The cells begin to be queued-up in the buffers. If this situation persists, the buffers get filled-up, and cells must be thrown away, or xe2x80x9cdroppedxe2x80x9d. A good design minimizes the number of dropped cells.
A highly effective buffer control strategy is dynamic input buffering and output control (DIBOC). In a DIBOC architecture, a switch fabric has an input side and an output side for switching cells received at any of a plurality of input ports to any of a plurality of output ports. Cells received at the input side and destined for the output side are buffered at the input side. The output side monitors the status of the output ports, and eventually transmits grants to release the cells buffered in the input side. Buffering cells at inputs controlled by outputs has numerous advantages. First, input buffering means that cells are dropped before being transmitted across the switch fabric whenever dropping is required, reducing the traffic load on the switch fabric during congested periods. Second, output control means that the switch may be designed according to output port bandwidth limitations, improving scalability. Third, output control means that precise control algorithms may be implemented to allocate grants in a fair manner, i.e., output control allows grants to be allocated in a logical order based on considerations such as source input port, cell priority and destination output port.
Known DIBOC architectures have relied on handshaking procedures in which requests and grants are exchanged on a xe2x80x9cper cellxe2x80x9d basis to secure release of cells. In such handshaking procedures, the input side transmits to the output side a request for release for each cell received. Such requests typically identify a logical output queue for the cell, e.g., the cell priority level, output, etc. The output side either queues the entire requests in an request buffer, as in Hayter, U.S. Pat. No. 5,448,559, or increments a xe2x80x9cbacklogxe2x80x9d value in a status buffer reserved for the logical output queue, as in Khacherian, application Ser. No. 08/679,360, U.S. Pat. No. 5,768,257, the output side""s issuance of a grant to release the cell across the switching fabric to the identified output. The grants are issued on a xe2x80x9cper cellxe2x80x9d basis in a logical order by arbitrating among the logical output queues having at least one request pending.
Despite the significant advantages of DIBOC as an overall buffer control strategy, there is room to improve on the xe2x80x9cper cellxe2x80x9d handshaking procedures implemented in known DIBOC architectures. Such handshaking procedures have several weaknesses. First, a request must be transmitted to the output side for each cell even though the cell""s logical output queue may already have a cell pending, resulting in the transmission of superfluous control traffic. Second, each request received by the output side must be queued even though the logical output queue with which the request is associated may already have a cell pending, or at the very least a multi-bit xe2x80x9cbacklogxe2x80x9d value must be retained and updated for each logical output queue, imposing unnecessary status buffering requirements. Third, whenever a request does not reach the output side due to a collision or corruption during transmission, the output side develops an inaccurate view of the status of a logical output queue, which is not easily remedied. Analogous weaknesses arise in connection with the transmission of grants to the input side on a xe2x80x9cper cellxe2x80x9d basis. Accordingly, there is a need for a novel buffer control strategy which provides the traditional advantages of DIBOC without the side effects of xe2x80x9cper cellxe2x80x9d handshaking.
In its most basic feature, the present invention provides a DIBOC buffer control strategy for a digital traffic switch which avoids the side effects of xe2x80x9cper cellxe2x80x9d handshaking through the expedient of queue status-based buffer control.
In one aspect of the invention, the transmission of requests on a xe2x80x9cper cellxe2x80x9d basis is eliminated by relying on changes in the content status of logical output queues from xe2x80x9cemptyxe2x80x9d to xe2x80x9cnot emptyxe2x80x9d, or vice versa, as the basic triggering event for transmitting status messages from the input side to the output side. A xe2x80x9cnot emptyxe2x80x9d status message for a logical output queue is transmitted whenever the. state of the logical output queue has changed from xe2x80x9cemptyxe2x80x9d to xe2x80x9cnot emptyxe2x80x9d. An xe2x80x9cemptyxe2x80x9d status message is transmitted whenever the state of a logical output queue has reverted to xe2x80x9cemptyxe2x80x9d. The content status of each logical output queue is monitored at the output side by retaining and updating a single status bit which has a particular binary value (e.g., a xe2x80x9c0xe2x80x9d) when the last-received status message indicates a logical output queue""s status as xe2x80x9cemptyxe2x80x9d and the opposite binary value (e.g., a xe2x80x9c1xe2x80x9d) when the last-received status message indicates a logical output queue""s status as xe2x80x9cnot emptyxe2x80x9d. The output side may then, in a logical order, grant clearance to logical output queues whose content status is indicated as xe2x80x9cnot emptyxe2x80x9d to release discrete information units from the input side to the output side. By limiting the transfer frequency and output-retained bit-count of content status information to the instances and information required to effectuate the logical order for granting clearance to release discrete information units, control traffic and status buffering requirements are reduced.
In another aspect, the transmission of grants on a xe2x80x9cper cellxe2x80x9d basis is eliminated by relying on changes in the clearance status of logical output queues from xe2x80x9cclear to releasexe2x80x9d to xe2x80x9cnot clear to releasexe2x80x9d, or vice versa, as the basic triggering event for transmitting status messages from the output side to the input side. A xe2x80x9cclear to releasexe2x80x9d status message for a logical output queue is transmitted whenever the status of the logical output queue has changed from xe2x80x9cnot clear to releasexe2x80x9d to xe2x80x9cclear to releasexe2x80x9d. A xe2x80x9cnot clear to releasexe2x80x9d status message is transmitted whenever the status of a logical output queue has reverted to xe2x80x9cnot clear to releasexe2x80x9d. The clearance status of each logical output queue is monitored at the input side by retaining and updating a single status bit which has a particular binary value (e.g., a xe2x80x9c0xe2x80x9d) when the last-received status message indicates logical output queue""s status as xe2x80x9cnot clear to releasexe2x80x9d and the opposite binary value (e.g., a xe2x80x9c1xe2x80x9d) when the last-received status message indicates logical output queue""s status as xe2x80x9cclear to releasexe2x80x9d. The input side may then, in a logical order, release discrete information units from logical output queues whose clearance status is indicated as xe2x80x9cclear to releasexe2x80x9d from the input side to the output side. By limiting the transfer frequency and input-retained bit-count of clearance status information to the instances and information required to effectuate the logical order for releasing discrete information units, control traffic and status buffering requirements are further reduced.
In yet another aspect, the present invention avoids another problem of xe2x80x9cper cellxe2x80x9d handshaking by re-transmitting the most recent content status (and clearance status) messages whenever extra bandwidth is available. By re-transmitting content status (and clearance status) messages, any inaccurate view of the content and clearance status of logical output queues which develops as a result of the failure of original content status (and clearance status) messages to be delivered is eventually cured, even if it is not known that the original transmission failed, and without adding bandwidth requirements.
Of course, the present invention need not by implemented reflexively. Content status messages may be used in conjunction with conventional xe2x80x9cper cellxe2x80x9d grants, rather than clearance status messages. Alternatively, clearance status messages may be used in conjunction with conventional xe2x80x9cper cellxe2x80x9d requests, rather than content status messages. Similarly, implementations are possible wherein content status messages are re-transmitted whereas clearance status messages are not, or vice versa.
These and other objects of the present invention may be better understood by reference to the following detailed description, taken in conjunction with the accompanying drawings which are briefly described below. Of course, the actual scope of the invention is defined by the appended claims.